<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1:

            输入: amount = 5, coins = [1, 2, 5]
            输出: 4
            解释: 有四种方式可以凑成总金额:

            5=5
            5=2+2+1
            5=2+1+1+1
            5=1+1+1+1+1
            示例 2:

            输入: amount = 3, coins = [2]
            输出: 0
            解释: 只用面额2的硬币不能凑成总金额3。
            示例 3:

            输入: amount = 10, coins = [10]
            输出: 1
            注意，你可以假设：

            0 <= amount (总金额) <= 5000
            1 <= coin (硬币面额) <= 5000
            硬币种类不超过 500 种
            结果符合 32 位符号整数

        */


        /*
            动态规划解法
        */
        var change = function(amount, coins) {
            // 初始化
            let dp = new Array(coins.length).fill(0).map(() => new Array(amount + 1).fill(0))
            // 第一个数必须是1
            dp[0][0] = 1
            // 初始化第一列
            for (let i = 0; i < coins.length; i++) {
                dp[i][0] = 1
            }   
            // 初始化第一行 j 从1开始
            for (let j = 1; j <= amount; j++) {
                dp[0][j] = dp[0][j - coins[0]]
            } 
            for (let i = 1; i < coins.length; i++) {
                for (let j = 1; j <= amount; j++) {
                    if (j < coins[i]) dp[i][j] = dp[i - 1][j]
                    else dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]
                }
            }   
            return dp[coins.length - 1][amount]
        };
        // console.log(change(5, [1, 2, 5]));
        console.log(change(3, [2]));
    </script>
</body>

</html>